package com.example.algorithm.backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * 二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
 * 例如，0011:011001二进制手表读取为 "3:25" 。
 * 给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
 * <p>
 * 小时不会以零开头：
 * 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。
 * 分钟必须由两位数组成，可能会以零开头：
 * 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。
 * <p>
 * 示例 1：
 * 输入：turnedOn = 1
 * 输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
 * <p>
 * 提示：
 * 0 <= turnedOn <= 10
 * <p>
 * Related Topics 位运算 回溯
 */
public class Leetcode401_ReadBinaryWatch {
    public static void main(String[] args) {

//        List<String> strings = new Solution().readBinaryWatch(1);
//        System.out.println(strings.size());
//        strings.forEach(e -> System.out.println(e));

        System.out.println(Integer.bitCount(18));

    }

    static class Solution {

        //LED灯，前四个为小时，后六个为分钟
        final int[] array = new int[]{8, 4, 2, 1, 32, 16, 8, 4, 2, 1};

        /**
         * 回溯解法二
         *
         * @param num
         * @return
         */
        public List readBinaryWatch3(int num) {
            List result = new ArrayList();
            //判断输入
            if (num < 0)
                return result;
            backTrack(num, 0, 0, 0, result);
            return result;
        }

        /**
         * @param num    需要亮灯的数量
         * @param start  开始位置
         * @param hour   已有 小时
         * @param minute 已有的 分钟
         */
        public void backTrack(int num, int start, int hour, int minute, List<String> result) {
            if (num == 0) { //需要亮0个等表示找到了一种组合，需要验证是否正确
                //判断时间是否正确
                if (hour > 11 || minute > 59)
                    return;
                StringBuilder tmp = new StringBuilder();
                //小时
                tmp.append(hour);
                tmp.append(":");
                //分钟
                if (minute < 10)
                    tmp.append(0);
                tmp.append(minute);
                // 符合时间规则加入到结果list中
                result.add(new String(tmp));
                return;
            }
            for (int i = start; i < array.length; i++) {
                /*回溯做选择*/
                //判断是小时还是分钟
                if (i < 4)//小时
                    hour += array[i];
                else
                    minute += array[i];
                //递归
                backTrack(num - 1, i + 1, hour, minute, result);
                /*回溯取消 本轮的选择 ，恢复原状*/
                if (i < 4)//小时
                    hour -= array[i];
                else
                    minute -= array[i];
            }
        }

        /**
         * 将时钟分成两部分来看
         * turnedOn的个数也要分成时域和分域来看
         * (比如 turnedOn = 5 则时域可能为1, 2, 3, 4(不可能大于4，因为时域总共只有四位) 对应的分域则为 4, 3, 2, 1)
         * 上下部分分别计算可能结果(回溯)，然后拼接在一起
         * @param turnedOn
         * @return
         */
        public List<String> readBinaryWatch2(int turnedOn) {
            List<String> res = new ArrayList<>();
            List<String> hourStrs = new ArrayList<>();
            List<String> minStrs = new ArrayList<>();
            for (int i = 0; i < 4 && i <= turnedOn; i++) { // 所有时域可能情况(时域"1"的个数确定了, 分域就确定了)
                makeStrs(hourStrs, new StringBuilder(), 4 - i, i); // 得到所有可能的时域的二进制字符串
                makeStrs(minStrs, new StringBuilder() ,6 - (turnedOn - i) , turnedOn - i);// 得到所有可能的分域的二进制字符串

                // 拼接结果
                hourStrs.forEach(hour -> {
                    minStrs.forEach(min -> {
                        int h = Integer.parseInt(hour, 2);
                        int m = Integer.parseInt(min, 2);
                        if (h > 11 || m > 59) {
                            return;
                        }
                        if (m < 10) {
                            res.add(h + ":0" + m);
                        } else {
                            res.add(h + ":" + m);
                        }
                    });
                });

                hourStrs.clear();
                minStrs.clear();
            }
            return res;
        }

        /**
         *
         * @param res 可能的二进制字符串
         * @param sb 初始StringBuilder
         * @param num0 二进制字符串中0的个数
         * @param num1 二进制字符串中1的个数
         */
        private void makeStrs(List<String>res, StringBuilder sb, int num0, int num1) {
            if ((num0 == 0) && (num1 == 0)) {
                res.add(sb.toString());
                return;
            }

            if (num0 > 0) {
                makeStrs(res, sb.append('0'), num0 - 1, num1);
                sb.deleteCharAt(sb.length() - 1); // 不符合条件，复原状态
            }

            if (num1 > 0) {
                makeStrs(res, sb.append('1'), num0, num1 - 1);
                sb.deleteCharAt(sb.length() - 1);// 不符合条件，复原状态
            }
        }

        /**
         * 解法一:枚举所有枚举时分，满足条件(时分的二进制位为1的相加等于turnedOn)的加入到结果集中
         *
         * 方法二：二进制枚举
         * 枚举所有 2^10=1024 种灯的开闭组合，即用一个二进制数表示灯的开闭，其高 4 位为小时，低 6 位为分钟。
         * 若小时和分钟的值均在合法范围内，且二进制中 1 的个数为 turnedOn，则将其加入到答案中。
         *。
         * @param turnedOn
         * @return
         */
        public List<String> readBinaryWatch1(int turnedOn) {
            List<String> res = new ArrayList<>();
            // 枚举时分
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 60; j++) {
                    if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
                        String min = (j < 10) ? ("0" + j) :( j + "");
                        res.add(i + ":" + min);
                    }
                }
            }

            // 枚举二进制
//            for (int i = 0; i < 1024; ++i) {
//                int h = i >> 6, m = i & 63; // 用位运算取出高 4 位和低 6 位
//                if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
//                    res.add(h + ":" + (m < 10 ? "0" : "") + m);
//                }
//            }


            return res;
        }

        public List<String> readBinaryWatch(int turnedOn) {
            return readBinaryWatch2(turnedOn);
        }
    }
}
